package com.dyz.leetcode;

public class MaxProfit309 {
    //动态规划dp[i] :
    //1. 当天不持有股票dp[i][0] --> (1) 今天卖的 dp[i][0]=dp[i-1][1]+prince[i] (2) 昨天就没有 d[i][0] = dp[i-1][0]
    //2  当天持有股票dp[i][1]  -->  (2)今天买的  dp[i][1] = d[i-2][0]-prince[i] (2)昨天就买了 dp[i][1] = dp[i-1][1]
    public int maxProfit(int[] prices) {
        if(prices==null||prices.length==0){return 0;}
        int len = prices.length;
        int [][] dp = new int[len][2];
        //base case
        dp[0][0] = 0;
        dp[0][1] = 0-prices[0];
        for(int i=1; i<len; i++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], ((i-2)>=0?dp[i-2][0]:0)-prices[i]);
        }
        return Math.max(dp[len-1][0], dp[len-1][1]);
    }
}
